from typing import List


class Solution:
    def scoreOfStudents(self, s: str, answers: List[int]) -> int:
        # ---------- 计算正确答案 ----------
        correct = eval(s)

        # ---------- 计算所有可能的错误答案 ----------
        s = "+" + s

        # 状态：[之前所有项的和，当前项的值]
        dp1 = {(0, 0)}
        for i in range(0, len(s), 2):
            sign = s[i]  # 符号
            num = int(s[i + 1])  # 数字
            dp2 = set()
            for last, now in dp1:
                if sign == "+":
                    dp2.add((last, now + num))  # 先计算加号
                    dp2.add((last + now, num))  # 后计算加号
                else:  # sign == "*"
                    dp2.add((last, now * num))  # 乘号作为加号位置的参考系，只有一个情况
            dp1 = dp2

        # 计算所有错误答案
        wrong = {last + now for last, now in dp1}

        print(correct, wrong)

        ans = 0
        for answer in answers:
            if answer == correct:
                ans += 5
            elif answer in wrong:
                ans += 2
        return ans


if __name__ == "__main__":
    print(Solution().scoreOfStudents(s="7+3*1*2", answers=[20, 13, 42]))  # 7
    print(Solution().scoreOfStudents(s="3+5*2", answers=[13, 0, 10, 13, 13, 16, 16]))  # 19
    print(Solution().scoreOfStudents(s="6+0*1", answers=[12, 9, 6, 4, 8, 6]))  # 10

    # 测试用例 27/274
    print(Solution().scoreOfStudents(s="1+2*3+4", answers=[13, 21, 11, 15]))  # 11
